package com.company.shuzhuAndString;

import com.sun.org.apache.regexp.internal.REUtil;
import org.junit.Test;
import sun.security.util.ArrayUtil;
import sun.security.util.Length;
import sun.text.CollatorUtilities;

import javax.swing.*;
import java.util.*;

/**
 * @description:
 * @author: Code-zyc
 * @date: Created in 2021/10/25 12:56
 * @version:
 * @modified By:
 */
public class test {
    public static void main(String[] args) {

        A a = new A();
//        a.show();

    }


    @Test
    public void mergeTest(){
        moveZeroes(new int[]{0,1,0,3,12});
    }

    /**
     * 移动零
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * */

    public void moveZeroes(int[] nums) {
        int start=0;
        int end=0;
        int length = nums.length;
        int temple;
        while (end<length){
            if (nums[end]!=0 && nums[start]==0){
                temple=nums[start];
                nums[start]=nums[end];
                nums[end]=temple;
                end++;
                start++;
            }else if (nums[start]==0 && nums[end]==0){
                end++;
            }else {
                end++;
                start++;
            }
        }
    }


    /**
     * 删除排序数组中的重复项
     * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
     *
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     *
     *  
     *
     * 说明:
     *
     * 为什么返回数值是整数，但输出的答案是数组呢?
     *
     * 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
     *
     * 你可以想象内部操作如下:
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/array-and-string/cq376/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。**/

    public int removeDuplicates(int[] nums) {
        int length = nums.length;
        int end=0;
        int start=0;
        while (end<length){
            if (nums[end]!=nums[start]){
                start++;
                nums[start]=nums[end];
            }
                end++;

        }
        return  start++;
    }


    /**
     * 寻找旋转排序数组中的最小值
     * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
     * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
     * 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
     * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
     *
     * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/array-and-string/c3ki5/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。**/

    public int findMin(int[] nums) {
        int length = nums.length;
        if (length==1){
            return nums[0];
        }
        if (nums[0]<nums[length-1]){
           return nums[0];
        }else {
            for (int i=0;i<length-1;i++){
                if (nums[i]>nums[i+1]){
                    return nums[i+1];
                }
            }
        }
        return 0;
    }

    /**
     * 反转字符串中的单词 III
     * 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
     *
     *  */
    public String reverseWords2(String s) {
        StringBuilder result = new StringBuilder();
        char[] chars = s.toCharArray();
        int start=0;
        int end=0;
        int temple=0;
       while (end<chars.length){
           if (chars[end]==' '){
               for (temple=end-1;temple>=start;temple--){
                   result.append(chars[temple]);
               }
               result.append(' ');
               end++;
               start=end;
           }else {
               end++;
           }
       }
       //最后一个
        for (temple=end-1;temple>=start;temple--){
            result.append(chars[temple]);
        }
        return  result.toString();
    }


    public List<Integer> getRow(int rowIndex) {

        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < rowIndex+1; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        return ret.get(rowIndex);
    }




    /**杨辉三角
     给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

     在「杨辉三角」中，每个数是它左上方和右上方的数的和。
     * **/
    public List<List<Integer>> generate(int numRows) {



        List<List<Integer>> result=new ArrayList<List<Integer>>();
        List<Integer> templr=new ArrayList<>();
        templr.add(1);
        result.add(templr);
        for (int i = 1; i < numRows; i++) {
            templr=new ArrayList<>();
            templr.add(1);
            for (int j=1;j<i;j++){
                templr.add(result.get(i-1).get(j)+result.get(i-1).get(j-1));
            }
            templr.add(1);
            result.add(templr);
        }

        return  result;
    }
    
    /**
     * 长度最小的子数组
     * 给定一个含有n个正整数的数组和一个正整数 target 。
     *
     * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/array-and-string/c0w4r/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
    public int minSubArrayLen(int target, int[] nums) {
        int minlength=Integer.MAX_VALUE;
        int length = nums.length;
        int start=0;
        int end=0;
        int temple=0;
        while (end<length){
            temple=temple+nums[end];
               while (temple>=target && start<length){
                   minlength=(end-start+1)<minlength?(end-start+1):minlength;
                   temple=temple-nums[start];
                   start++;
               }
               end++;

        }
        return minlength==Integer.MAX_VALUE?0:minlength;
    }


    /**
     * 最大连续1的个数
     * 给定一个二进制数组， 计算其中最大连续 1 的个数。
     *
     *
     */

    public int findMaxConsecutiveOnes(int[] nums) {
        int max=0;
        int temp=0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]==1){
                while (i < nums.length &&nums[i]==1 ){
                    temp++;
                    i++;
                }
                if (temp>max){
                    max=temp;
                }
                temp=0;
            }
        }
        return max;
    }
    /**
     * 移除元素
     * 给你一个数组 nums和一个值 val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。
     *
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     *
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     *
     * 
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/array-and-string/cwuyj/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。***/
    public int removeElement(int[] nums, int val) {
        int fast=0;
        int slow=0;
        int length = nums.length;
        while (fast<length && slow<length){
            if (nums[fast]!=val ){
                nums[slow]=nums[fast];
                slow++;
            }

            fast++;
        }
        return slow;
    }
    
    
    /**
     * 两数之和 II - 输入有序数组
     * 给定一个已按照 非递减顺序排列 的整数数组numbers ，请你从数组中找出两个数满足相加之和等于目标数target 。
     *
     * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
     *
     * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
     *
     * 
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/array-and-string/cnkjg/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。**/
    public int[] twoSum(int[] numbers, int target) {
        int length = numbers.length;
        for (int i = 0; i < length-1; i++) {
            int j=i+1;
            while (j<length){
                if(numbers[i]+numbers[j]<target){
                    j++;
                }else if(numbers[i]+numbers[j]>target){
                    break;
                }else {
                    return new int[]{i+1,j+1};
                }

            }
        }

        return null;
    }
    
    /**
     * 数组拆分 I
     * 给定长度为2n的整数数组 nums ，你的任务是将这些数分成n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到n 的 min(ai, bi) 总和最大。
     *
     * 返回该 最大总和 。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/array-and-string/c24he/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。**/
    public int arrayPairSum(int[] nums) {

        int result=0;
        Arrays.sort(nums);
        for (int i=0;i<nums.length;i=i+2){
            result=nums[i]+result;
        }
        return result;
    }
    /**
     * 反转字符串
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     *
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     ***/
    public void reverseString(char[] s) {
        char templ;
        int length=s.length;
        for (int i = 0; i <length/2; i++) {
            templ=s[i];
            s[i]=s[length-i-1];
            s[length-i-1]=templ;
        }
    }

    /**
     * 实现strStr()函数。
     * 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
     * 说明：
     * 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
     * 对于本题而言，当needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。

     * **/
    public int strStr(String haystack, String needle) {
        if (needle.equals("")){
            return 0;
        }
        char[] ha = haystack.toCharArray();
        char[] ne = needle.toCharArray();
        int j=0;
        for (int i = 0; i < ha.length; i++) {
            if(ha[i]==ne[j]){
                int t=i;
                while ( j<ne.length &&t<ha.length && ha[t]==ne[j] ){
                    if(j==ne.length-1){
                        return t-j;
                    }
                    t++;
                    j++;

                }
                j=0;
            }
        }
        return -1;
    }

   /** 翻转字符串里的单词

    给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

    单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

    请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

    说明：

    输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
    翻转后单词间应当仅用一个空格分隔。
    翻转后的字符串中不应包含额外的空格。*/

    public String reverseWords(String s) {
        int length = s.length();
        char[] chars = s.toCharArray();
        ArrayList<StringBuffer> result=new ArrayList<>();
        for (int i = 0; i < length; i++) {
            if (chars[i]!=' '){
                StringBuffer stringBuffer = new StringBuffer();
                while (i<length&&chars[i]!=' '){
                    stringBuffer.append(chars[i]);
                    i++;
                }
                result.add(stringBuffer);
            }

        }
        StringBuffer stringBuffer = new StringBuffer();
        for (int i = result.size()-1; i > 0; i--) {
            stringBuffer.append(result.get(i));
            stringBuffer.append(" ");
        }
        stringBuffer.append(result.get(0));
        return stringBuffer.toString();
    }

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();

        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (charArray[i]!=charArray[j]){
                    dp[i][j]=false;
                }else {
                    if(j-i<3){
                        dp[i][j]=true;
                    }else {
                        dp[i][j]=dp[i+1][j-1];
                    }
                }

                if(dp[i][j]&& j-i+1>maxLen){
                    maxLen=j-i+1;
                    begin=i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }



    //      给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
    public int[] findDiagonalOrder(int[][] mat) {
        ArrayList<Integer> list=new ArrayList<>();
        ArrayList<Integer> templlist=new ArrayList<>();
        int xlength=mat.length;
        int ylength=mat[0].length;
        boolean flag=false; //true  代表是不需要反转

        int i=0;
        int j=0;
        while (i<=xlength && j<=ylength){
            if(flag){
                while (i>=0 && j>=0 && i<xlength&&j<ylength){
                    list.add(mat[i][j]);
                    i++;
                    j--;
                }
                flag=!flag;

            }else {
                while (i>=0 && j>=0 && i<xlength&&j<ylength){
                    templlist.add(mat[i][j]);
                    i++;
                    j--;
                }
                //进行反转
                for (int k = templlist.size()-1; k >= 0; k--) {
                    list.add(templlist.remove(k));
                }
                flag=!flag;

            }
            //把起点移到对角线
            int t=i;
            i=j+1;
            j=t;
            if(i>=xlength || j>=ylength){
                i=i+1;
                j=j-1;
            }

        }
        int size = list.size();
        int[] result=new int[size];
        for (int i1 = 0; i1 < size; i1++) {
            result[i1]=list.get(i1);
        }

        return result ;

    }



//      给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
    public int[] findDiagonalOrder2(int[][] mat) {
            int xlength=mat.length;
            int ylength=mat[0].length;
            int[] result=new int[xlength*ylength];
            if(xlength==1){
                for (int i = 0; i < ylength; i++) {
                   result[i]=mat[0][i];
                }
                return result;
            }
            if(ylength==1){
                for (int i = 0; i < ylength; i++) {
                    result[i]=mat[0][i];
                }
                return result;
            }

            result[0]=mat[0][0];
            int i=0;
            int j=0;
            int count=0;
        while (i<xlength-1 && j<ylength-1){

            if(i==0){ //表示在第一行  该 先向右移动 再向左下的移动
                j++; //向左移动
                while (j>0){
                    count++;
                    i++;
                    j--;
                    result[count]=mat[i][j];
                }
            }
            if(j==0){ //表示在第一列 先向下  再向左上移动
                while (i>0){
                    count++;
                    i--;
                    j++;
                    result[count]=mat[i][j];
                }
            }

        }

        result[count+1]=mat[i][j]; //把最后一个数据加上去
        return result;

    }

    //编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
    public void setZeroes(int[][] matrix) {
        Set<Integer> x=new HashSet();
        Set<Integer> y=new HashSet();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j]==0){
                   x.add(i);
                    y.add(j);
                }
            }
        }
        for (Integer item:x){
            //把这一行都变成0
            for (int i = 0; i < matrix[0].length; i++) {
                matrix[item][i]=0;
            }
        }

        for (Integer item:y){
            //把这一列都变成0
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][item]=0;
            }
        }

        return;
    }


//给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
//
//不占用额外内存空间能否做到？
    public void rotate(int[][] matrix) {

            int n=matrix.length;
            int[][] temple=new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temple[j][n-i-1]=matrix[i][j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j]=temple[i][j];
            }
        }

    }

    public String longestCommonPrefix(String[] strs) {
        int length = strs.length;
        if(length==0){
            return "";
        }
        if(length==1){
            return strs[0];
        }
        String longestPrefix=strs[0];
        for (int i = 1; i < length; i++) {
            longestPrefix=longestPrefix(longestPrefix,strs[i]);
        }
        return  longestPrefix;
    }

    public String longestPrefix(String s1,String s2){
        int min = Math.min(s1.length(), s2.length());
        int i ;
        for (i=0; i < min ; i++) {
            if(s1.charAt(i)!=s2.charAt(i)){
                break;
            }
        }
        return s1.substring(0, i);
    }

    public int[][] merge(int[][] intervals) {
        //按左区间进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        int left = intervals[0][0];
        int right=intervals[0][1];
        List<int[]> result=new ArrayList<>();

        for (int i = 1; i < intervals.length; i++) {

            //右边可以更新
            if(intervals[i][0]<=right && intervals[i][1]>=right){

                right=intervals[i][1];
            }else if(intervals[i][0]<=left ){   //左边可以更新
                left=intervals[i][0];
            }else if(intervals[i][0]>=left && intervals[i][1]<=right) {//不可以更新 但是可以被吃
                //啥也不干
            }else {
                //表示 不能合并  把最新的区间填入到结果中
                result.add(new int[]{left,right});

                //再把left 与right 进行更新
                left=intervals[i][0];
                right=intervals[i][1];
            }


        }
        result.add(new int[]{left,right});


        return result.toArray(new int[result.size()][]);
    }
}
